import collections
from typing import List


class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        size = len(nums)

        # 定义状态矩阵
        dp1 = [collections.Counter() for _ in range(size)]  # 只有2个数(只有1个差)的等差数列的数量
        dp2 = [collections.Counter() for _ in range(size)]  # 大于等于3个数(超过2个差)的等差数列的数量

        ans = 0

        for i in range(size):
            ans += sum(dp2[i].values())

            for j in range(i + 1, size):
                d = nums[j] - nums[i]

                # 记录nums[i]和nums[j]构成的只有2个数的等差数列的情况
                dp1[j][d] += 1

                if d in dp1[i]:
                    dp2[j][d] += dp1[i][d]
                if d in dp2[i]:
                    dp2[j][d] += dp2[i][d]

        # print([dict(elem) for elem in dp1])
        # print([dict(elem) for elem in dp2])

        return ans


if __name__ == "__main__":
    print(Solution().numberOfArithmeticSlices([2, 4, 6, 8, 10]))  # 7

    # 测试用例1
    print(Solution().numberOfArithmeticSlices([7, 7, 7, 7, 7]))  # 16

    # 测试用例65
    print(Solution().numberOfArithmeticSlices([2, 2, 3, 4]))  # 2
